<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>快速排序</title>
</head>

<body>
  <script type="text/javascript">
    /* 
       quick: 实现快速排序
         @params
           ary [array] 需要排序的数组
         @return
           [array] 排序后的新数组
      */

    function quick(ary) {
      // 4、结束递归（当 ary 中小于等于一项，则不用处理）
      if (ary.length <= 1) {
        return ary;
      }
      // 1、找到数组的中间项，在原有的数组中把它移除
      let middleIndex = Math.floor(ary.length / 2);
      let middValue = ary.splice(middleIndex, 1)[0];

      // 2、准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左边数组中，反之放到右边数组中
      let aryLeft = [],
        aryRight = [];
      for (let i = 0; i < ary.length; i++) {
        let item = ary[i];
        item < middValue ? aryLeft.push(item) : aryRight.push(item);
      }
      // 3、递归方式让左右两边的数组持续这样处理，一直到左右两边都排好序为止
      //    最后让左边 + 中间 + 右边 拼接成为最后的结果
      return quick(aryLeft).concat(middValue, quick(aryRight));
    }
    let ary = [12, 8, 15, 16, 1, 24]
    ary = insert(ary);
    console.log(ary)
  </script>
</body>

</html>